TNotes.leetcode

Appearance

0680. 验证回文串 II【简单】

0680. 验证回文串 II【简单】 ​

1. 📝 题目描述 ​

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false。

示例 1：

txt
输入：s = "aba"
输出：true

示例 2：

txt
输入：s = "abca"
输出：true
解释：你可以删除字符 'c'。

示例 3：

txt
输入：s = "abc"
输出：false

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成

2. 🎯 s.1 - 双指针法 ​

js
/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  let left = 0
  let right = s.length - 1

  // 判断子串是否为回文串的辅助函数
  const isPalindrome = (str, start, end) => {
    while (start < end) {
      if (str[start] !== str[end]) {
        return false
      }
      start++
      end--
    }
    return true
  }

  while (left < right) {
    if (s[left] !== s[right]) {
      // 当遇到不匹配的字符时，尝试删除左边或右边的字符
      return (
        isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1)
      )
    }
    left++
    right--
  }

  // 如果没有遇到不匹配的字符，本身就是回文串
  return true
}
  • 时间复杂度：O(n)，其中 n 是字符串的长度，最坏情况下需要遍历字符串两次
  • 空间复杂度：O(1)，只使用了常数个额外变量
  • 算法思路：
    • 使用双指针从两端向中间扫描，当遇到不匹配的字符时，尝试删除左边或右边的字符，看是否能形成回文串。

Discussions